package cn.cxq.learning.graph;

import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 无向图
 */
public class UndirectedGraph {

    private List<String> vertexList;  //顶点集合
    private int[][] adjacencyMatrix;  //邻接矩阵
    private int numOfEdges;  //边的数目

    public UndirectedGraph(String[] vertexes, int[][] edges) {

        vertexList = new ArrayList<>();

        for (int i = 0; i < vertexes.length; i++) {
            vertexList.add(vertexes[i]);
        }
        adjacencyMatrix = new int[vertexList.size()][vertexList.size()];

        //初始化邻接矩阵
        for (int i = 0; i < edges.length; i++) {
            adjacencyMatrix[edges[i][0]][edges[i][1]] = edges[i][2];
            adjacencyMatrix[edges[i][1]][edges[i][0]] = edges[i][2];
        }

        numOfEdges = edges.length;
    }

    /**
     * 打印邻接矩阵
     */
    public void printAdjacencyMatrix() {
        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            for (int j = 0; j < this.adjacencyMatrix[i].length; j++) {
                System.out.print(adjacencyMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 获取第一个相邻节点
     *
     * @param v 目标节点
     * @return 第一个相邻节点下标
     */
    public int getFirstNeighbor(int v) {
        for (int i = 0; i < getNumOfVertexes(); i++) {
            if (this.adjacencyMatrix[v][i] != 0) return i;
        }

        return -1;
    }

    /**
     * 获取下一个相邻节点下标
     *
     * @param v1 目标节点
     * @param v2 这次的相邻节点下标
     * @return 下一个相邻节点下标
     */
    public int getNextNeighbor(int v1, int v2) {
        for (int i = v2 + 1; i < getNumOfVertexes(); i++) {
            if (this.adjacencyMatrix[v1][i] != 0) return i;
        }
        return -1;
    }

    /**
     * 深度优先遍历
     */
    public void dfs() {
        boolean[] visited = new boolean[getNumOfVertexes()];

        for (int i = 0; i < getNumOfVertexes(); i++) {
            if (!visited[i]) dfs(visited, i);
        }

    }

    private void dfs(boolean[] visited, int index) {
        System.out.print(vertexList.get(index) + "--->");
        visited[index] = true;

        int neighbor = getFirstNeighbor(index);

        while (neighbor != -1) {
            if (!visited[neighbor]) dfs(visited, neighbor);
            neighbor = getNextNeighbor(index, neighbor);
        }
    }

    public void bfs(boolean[] visited, int index) {

        ArrayList<Integer> nextToList = new ArrayList<>();

        int neighbor = getFirstNeighbor(index);

        while (neighbor != -1) {
            if (!visited[neighbor]) {
                System.out.print(vertexList.get(neighbor) + "--->");
                visited[neighbor] = true;
                nextToList.add(neighbor);
            }

            neighbor = getNextNeighbor(index, neighbor);
        }

        if (nextToList.size() > 0) {
            Integer nextIndex = nextToList.get(0);
            nextToList.remove(0);
            bfs(visited, nextIndex);
        }

    }

    /**
     * 广度优先遍历
     */
    public void bfs() {

        boolean[] visited = new boolean[getNumOfVertexes()];

        System.out.print(vertexList.get(0) + "--->");
        visited[0] = true;

        for (int i = 0; i < getNumOfVertexes(); i++) {
            bfs(visited, i);
        }
    }

    /**
     * 普利姆算法求最小生成树
     */
    public void prim() {

        //记录节点是否在联通范围内
        boolean[] visited = new boolean[getNumOfVertexes()];

        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        visited[0] = true;

        //需要进行比顶点数少一次的遍历（取比顶点数少一哥的边）
        for (int term = 1; term < getNumOfVertexes(); term++) {
            int indexOfVisited = 0, indexOfNext = 0, min = Integer.MAX_VALUE;
            for (int i = 0; i < getNumOfVertexes(); i++) {
                for (int j = 0; j < getNumOfVertexes(); j++) {
                    if (visited[i] && !visited[j] && this.adjacencyMatrix[i][j] != 0 && this.adjacencyMatrix[i][j] < min) {
                        min = this.adjacencyMatrix[i][j];
                        indexOfVisited = i;
                        indexOfNext = j;
                    }
                }
            }
            visited[indexOfNext] = true;
            System.out.println("路径: " + vertexList.get(indexOfVisited) + "==>" + vertexList.get(indexOfNext) + "\n路程: " + this.adjacencyMatrix[indexOfVisited][indexOfNext] + "\n");
        }
    }

    /**
     * 克鲁斯卡尔算法，先将所有路径排序，然后按顺序去路径，只要不构成闭环就一直取
     */
    public void kruskal() {

        ArrayList<int[]> paths = new ArrayList<>(); //第一位表示路径长度，第二位第三位表示顶点

        //将所有的路径取出,并排序(升序)
        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            for (int j = i + 1; j < this.adjacencyMatrix[i].length; j++) {
                if (this.adjacencyMatrix[i][j] != 0) {
                    paths.add(new int[]{this.adjacencyMatrix[i][j], i, j});
                }
            }
        }

        paths.sort(Comparator.comparingInt(path -> path[0]));

        //利用并查集的特点来防止出现环
        int[] parent = new int[getNumOfVertexes()]; // 记录每个节点的父节点

        for (int i = 0; i < parent.length; i++) {
            parent[i] = i; //让每个节点开始都指向自己（自成一树）
        }

        int numOfEdges = 0; //计边数，保证比定点数少一的边数
        for (int[] path : paths) {
            int root1 = getVertexRoot(path[1], parent);
            int root2 = getVertexRoot(path[2], parent);

            if (root1 != root2) {
                System.out.println("路径: " + vertexList.get(path[1]) + "==>" + vertexList.get(path[2]) + "\n路程: " + path[0] + "\n");
                parent[root2] = root1;
                numOfEdges++;
            }

            if (numOfEdges == getNumOfVertexes() - 1) {
                break;
            }
        }
    }

    private int getVertexRoot(int i, int[] parent) {
        while (parent[i] != i) {
            i = parent[i];
        }
        return i;
    }

    /**
     * 迪杰斯特拉算法，求一个顶点到其他顶点的最短路径
     *
     * @param index
     */
    public int[] dijkstra(int index) {

        //判断是否已被访问
        boolean[] visited = new boolean[getNumOfVertexes()];

        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        visited[index] = true; //将当前节点设为已访问

        //存放最短路径，动态更新
        int[] shortest = new int[getNumOfVertexes()];

        for (int i = 0; i < shortest.length; i++) {
            shortest[i] = 0;
        }

        ArrayList<int[]> paths = new ArrayList<>(); //第一位表示路径长度，第二位第三位表示顶点

        //将所有的路径取出,并排序(升序) 顶点编号小的将会存在path[1] 大的在path[2]
        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            for (int j = i + 1; j < this.adjacencyMatrix[i].length; j++) {
                if (this.adjacencyMatrix[i][j] != 0) {
                    paths.add(new int[]{this.adjacencyMatrix[i][j], i, j});
                }
            }
        }

        paths.sort(Comparator.comparingInt(path -> path[0]));

        while (true) {

            int[] min = new int[]{Integer.MAX_VALUE};
            int shortestPlan = Integer.MAX_VALUE;

            for (int[] path : paths) {
                //每一次遍历寻找出发点是已经访问过的节点（visited[i] = true） 然后取其中最小的一个路径
                if (visited[path[1]] && !visited[path[2]] && path[0] + shortest[path[1]] < shortestPlan) { //使用一个int类型元素来记录最短总路径，min中存的只是单条路径，并不是总路径
                    min = path;
                    shortestPlan = path[0] + shortest[path[1]];
                }

                if (!visited[path[1]] && visited[path[2]] && path[0] + shortest[path[2]] < shortestPlan) { //修复了bug，无向图无所谓的起点和终点可言，都是可以当头作尾的
                    min = path;
                    shortestPlan = path[0] + shortest[path[2]];
                }
            }

            if (min[0] != Integer.MAX_VALUE) {
                if (visited[min[1]]) {
                    shortest[min[2]] = shortest[min[1]] + min[0]; //将当前顶点到该顶点的最小值累加存入shortest数组
                    visited[min[2]] = true;
                } else {
                    shortest[min[1]] = shortest[min[2]] + min[0]; //将当前顶点到该顶点的最小值累加存入shortest数组
                    visited[min[1]] = true;
                }

            } else {
                break;
            }
        }

        return shortest;
    }

    /**
     * 迪杰斯特拉算法，求一个顶点到其他顶点的最短路径
     *
     * @param index
     */
    public Map<Integer, List<int[]>> dijkstraForMap(int index) {

        //用来存放最短路径
        Map<Integer, List<int[]>> shortestPathMap = new HashMap<>();

        //判断是否已被访问
        boolean[] visited = new boolean[getNumOfVertexes()];

        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        visited[index] = true; //将当前节点设为已访问

        ArrayList<int[]> paths = new ArrayList<>(); //第一位表示路径长度，第二位第三位表示顶点

        //将所有的路径取出,并排序(升序) 顶点编号小的将会存在path[1] 大的在path[2]
        for (int i = 0; i < this.adjacencyMatrix.length; i++) {
            for (int j = i + 1; j < this.adjacencyMatrix[i].length; j++) {
                if (this.adjacencyMatrix[i][j] != 0) {
                    paths.add(new int[]{this.adjacencyMatrix[i][j], i, j});
                }
            }
        }

        paths.sort(Comparator.comparingInt(path -> path[0]));

        while (true) {

            int[] min = new int[]{Integer.MAX_VALUE};
            int shortestPlan = Integer.MAX_VALUE;

            for (int[] path : paths) {

                AtomicInteger preShortest1 = new AtomicInteger(); //目标顶点到前驱的最短路径
                List<int[]> preShortestList1 = shortestPathMap.get(path[1]);
                if (preShortestList1 != null) {
                    preShortestList1.forEach(shortest -> preShortest1.addAndGet(shortest[0]));
                }
                //每一次遍历寻找出发点是已经访问过的节点（visited[i] = true） 然后取其中最小的一个路径
                if (visited[path[1]] && !visited[path[2]] && path[0] + preShortest1.intValue() < shortestPlan) {
                    min = path;
                    shortestPlan = path[0] + preShortest1.intValue();
                }

                AtomicInteger preShortest2 = new AtomicInteger(); //目标顶点到前驱的最短路径
                List<int[]> preShortestList2 = shortestPathMap.get(path[2]);
                if (preShortestList2 != null) {
                    preShortestList2.forEach(shortest -> preShortest2.addAndGet(shortest[0]));
                }

                //每一次遍历寻找出发点是已经访问过的节点（visited[i] = true） 然后取其中最小的一个路径
                if (visited[path[2]] && !visited[path[1]] && path[0] + preShortest2.intValue() < shortestPlan) { //修复了bug，无向图无所谓的起点和终点可言，都是可以当头作尾的
                    min = path;
                    shortestPlan = path[0] + preShortest2.intValue();
                }
            }

            if (min[0] != Integer.MAX_VALUE) {
                if (visited[min[1]]) {
                    //将当前顶点到该顶点的最小值累加存入集合
                    List<int[]> preShortest = shortestPathMap.get(min[1]); //直至上一顶点的最短路径
                    ArrayList<int[]> shortest = new ArrayList<>(); //到当前顶点的最短路径
                    if (preShortest != null) shortest.addAll(preShortest);
                    shortest.add(min); //加入最后一条路径

                    shortestPathMap.put(min[2], shortest); //完成

                    visited[min[2]] = true;
                } else {
                    //将当前顶点到该顶点的最小值累加存入集合
                    List<int[]> preShortest = shortestPathMap.get(min[2]); //直至上一顶点的最短路径
                    ArrayList<int[]> shortest = new ArrayList<>(); //到当前顶点的最短路径
                    if (preShortest != null) shortest.addAll(preShortest);
                    shortest.add(min); //加入最后一条路径

                    shortestPathMap.put(min[1], shortest); //完成

                    visited[min[1]] = true;
                }

            } else {
                break;
            }
        }

        return shortestPathMap;
    }

    /**
     * 弗洛伊德算法（求所有顶点到其他顶点的最短路径）
     *
     * @return
     */
    public int[][] floyd() {

        int[][] shortestDist = this.adjacencyMatrix.clone();
        int[][] shortestPath = new int[getNumOfVertexes()][getNumOfVertexes()];

        for (int i = 0; i < shortestDist.length; i++) {
            for (int j = 0; j < shortestDist[0].length; j++) {
                if (i != j && shortestDist[i][j] == 0) {
                    shortestDist[i][j] = Integer.MAX_VALUE;
                } else {
                    shortestPath[i][j] = j;
                }
            }
        }

        for (int term = 0; term < getNumOfVertexes(); term++) {
            for (int i = 0; i < shortestDist.length; i++) {
                for (int j = 0; j < shortestDist[0].length; j++) {

                    int temp = (shortestDist[i][term] == Integer.MAX_VALUE || shortestDist[term][j] == Integer.MAX_VALUE) ? Integer.MAX_VALUE : shortestDist[i][term] + shortestDist[term][j];

                    if (shortestDist[i][j] > temp) {
                        shortestDist[i][j] = temp;
                        shortestPath[i][j] = term;  //从i到j需要经过term。
                    }
                }
            }
        }


        for (int i = 0; i < shortestPath.length; i++) {
            Stack<Integer> stack = new Stack<>(); //使用栈配合shortestPath数组还原路径
            for (int j = 0; j < shortestPath.length; j++) {
                if (i != j) {
                    int index = j;
                    while (shortestPath[i][index] != index) {
                        stack.add(shortestPath[i][index]);
                        index = shortestPath[i][index];
                    }

                    System.out.println(vertexList.get(i) + "==>" + vertexList.get(j));
                    System.out.println("途经:");

                    if (stack.size() == 0) {
                        System.out.println("直达~~~");
                    } else {
                        while (stack.size() != 0) {
                            System.out.println(vertexList.get(stack.pop()));
                        }
                    }

                    System.out.println("总路程:" + shortestDist[i][j]);
                    System.out.println("---------------------------------------------------------------");
                }
            }
            System.out.println("---------------------------------------------------------------");
        }


        return shortestDist;
    }


    /**
     * 获取顶点个数
     */
    public int getNumOfVertexes() {
        return this.vertexList.size();
    }

    public List<String> getVertexList() {
        return vertexList;
    }

    public void setVertexList(List<String> vertexList) {
        this.vertexList = vertexList;
    }

    public int[][] getAdjacencyMatrix() {
        return adjacencyMatrix;
    }

    public void setAdjacencyMatrix(int[][] adjacencyMatrix) {
        this.adjacencyMatrix = adjacencyMatrix;
    }

    public int getNumOfEdges() {
        return numOfEdges;
    }

    public void setNumOfEdges(int numOfEdges) {
        this.numOfEdges = numOfEdges;
    }

}
